{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import *\n",
    "from numpy import linalg as la\n",
    "\n",
    "def loadExData():\n",
    "    return[[0, 0, 0, 2, 2],\n",
    "           [0, 0, 0, 3, 3],\n",
    "           [0, 0, 0, 1, 1],\n",
    "           [1, 1, 1, 0, 0],\n",
    "           [2, 2, 2, 0, 0],\n",
    "           [5, 5, 5, 0, 0],\n",
    "           [1, 1, 1, 0, 0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  9.64365076e+00,   5.29150262e+00,   7.17576917e-16,\n",
       "         7.36147444e-17,   1.74873814e-33])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Data=loadExData()\n",
    "U,Sigma,VT=linalg.svd(Data)\n",
    "Sigma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "Sig3=mat([[Sigma[0], 0, 0], [0, Sigma[1], 0], [0, 0, Sigma[2]]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ -1.04434264e-15,   3.20656449e-16,   7.23686187e-16,\n",
       "           2.00000000e+00,   2.00000000e+00],\n",
       "        [ -6.65185002e-16,   4.50721154e-16,   2.14463848e-16,\n",
       "           3.00000000e+00,   3.00000000e+00],\n",
       "        [ -2.01858916e-16,   1.49573238e-16,   5.22856782e-17,\n",
       "           1.00000000e+00,   1.00000000e+00],\n",
       "        [  1.00000000e+00,   1.00000000e+00,   1.00000000e+00,\n",
       "           6.95875223e-17,   6.95875223e-17],\n",
       "        [  2.00000000e+00,   2.00000000e+00,   2.00000000e+00,\n",
       "           1.39175045e-16,   1.39175045e-16],\n",
       "        [  5.00000000e+00,   5.00000000e+00,   5.00000000e+00,\n",
       "           3.99672720e-17,   3.99672720e-17],\n",
       "        [  1.00000000e+00,   1.00000000e+00,   1.00000000e+00,\n",
       "           6.95875223e-17,   6.95875223e-17]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U[:, :3]*Sig3*VT[:3, :]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ecludSim(inA,inB):\n",
    "    return 1.0/(1.0 + la.norm(inA - inB))\n",
    "\n",
    "def pearsSim(inA,inB):\n",
    "    if len(inA) < 3 : return 1.0\n",
    "    return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1]\n",
    "\n",
    "def cosSim(inA,inB):\n",
    "    num = float(inA.T*inB)\n",
    "    denom = la.norm(inA)*la.norm(inB)\n",
    "    return 0.5+0.5*(num/denom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.12973190755680383"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myMat=mat(loadExData())\n",
    "ecludSim(myMat[:, 0], myMat[:, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ecludSim(myMat[:, 0], myMat[:, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosSim(myMat[:, 0], myMat[:, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cosSim(myMat[:, 0], myMat[:, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.20596538173840329"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pearsSim(myMat[:, 0], myMat[:, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pearsSim(myMat[:, 0], myMat[:, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def standEst(dataMat, user, simMeas, item):\n",
    "    n = shape(dataMat)[1]\n",
    "    simTotal = 0.0; ratSimTotal = 0.0\n",
    "    for j in range(n):\n",
    "        userRating = dataMat[user,j]\n",
    "        if userRating == 0: continue\n",
    "        overLap = nonzero(logical_and(dataMat[:,item].A>0, \\\n",
    "                                      dataMat[:,j].A>0))[0]\n",
    "        if len(overLap) == 0: similarity = 0\n",
    "        else: similarity = simMeas(dataMat[overLap,item], \\\n",
    "                                   dataMat[overLap,j])\n",
    "        print('the %d and %d similarity is: %f' % (item, j, similarity))\n",
    "        simTotal += similarity\n",
    "        ratSimTotal += similarity * userRating\n",
    "    if simTotal == 0: return 0\n",
    "    else: return ratSimTotal/simTotal\n",
    "\n",
    "def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst):\n",
    "    unratedItems = nonzero(dataMat[user,:].A==0)[1]#find unrated items \n",
    "    if len(unratedItems) == 0: return 'you rated everything'\n",
    "    itemScores = []\n",
    "    for item in unratedItems:\n",
    "        estimatedScore = estMethod(dataMat, user, simMeas, item)\n",
    "        itemScores.append((item, estimatedScore))\n",
    "    return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[4, 4, 0, 2, 2],\n",
       "        [4, 0, 0, 3, 3],\n",
       "        [4, 0, 0, 1, 1],\n",
       "        [1, 1, 1, 2, 0],\n",
       "        [2, 2, 2, 0, 0],\n",
       "        [5, 5, 5, 0, 0],\n",
       "        [1, 1, 1, 0, 0]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myMat=mat(loadExData())\n",
    "myMat[0,1]=myMat[0,0]=myMat[1,0]=myMat[2,0]=4\n",
    "myMat[3,3]=2\n",
    "myMat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 1 and 0 similarity is: 1.000000\n",
      "the 1 and 3 similarity is: 0.928746\n",
      "the 1 and 4 similarity is: 1.000000\n",
      "the 2 and 0 similarity is: 1.000000\n",
      "the 2 and 3 similarity is: 1.000000\n",
      "the 2 and 4 similarity is: 0.000000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(2, 2.5), (1, 2.0243290220056256)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recommend(myMat, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 1 and 0 similarity is: 1.000000\n",
      "the 1 and 3 similarity is: 0.309017\n",
      "the 1 and 4 similarity is: 0.333333\n",
      "the 2 and 0 similarity is: 1.000000\n",
      "the 2 and 3 similarity is: 0.500000\n",
      "the 2 and 4 similarity is: 0.000000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(2, 3.0), (1, 2.8266504712098603)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recommend(myMat, 2, simMeas=ecludSim)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 1 and 0 similarity is: 1.000000\n",
      "the 1 and 3 similarity is: 1.000000\n",
      "the 1 and 4 similarity is: 1.000000\n",
      "the 2 and 0 similarity is: 1.000000\n",
      "the 2 and 3 similarity is: 1.000000\n",
      "the 2 and 4 similarity is: 0.000000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(2, 2.5), (1, 2.0)]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recommend(myMat, 2, simMeas=pearsSim)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loadExData2():\n",
    "    return[[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5],\n",
    "           [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3],\n",
    "           [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0],\n",
    "           [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0],\n",
    "           [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0],\n",
    "           [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0],\n",
    "           [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1],\n",
    "           [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4],\n",
    "           [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2],\n",
    "           [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0],\n",
    "           [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "U,Sigma,VT=la.svd(mat(loadExData2()))\n",
    "myMat=mat(loadExData2())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 15.77075346,  11.40670395,  11.03044558,   4.84639758,\n",
       "         3.09292055,   2.58097379,   1.00413543,   0.72817072,\n",
       "         0.43800353,   0.22082113,   0.07367823])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sigma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "Sig2=Sigma**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "541.9999999999992"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(Sig2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "487.79999999999927"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(Sig2)*0.9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "378.82955951135773"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(Sig2[:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "500.50028912757909"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(Sig2[:3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def svdEst(dataMat, user, simMeas, item):\n",
    "    n = shape(dataMat)[1]\n",
    "    simTotal = 0.0; ratSimTotal = 0.0\n",
    "    U,Sigma,VT = la.svd(dataMat)\n",
    "    Sig4 = mat(eye(4)*Sigma[:4]) #arrange Sig4 into a diagonal matrix\n",
    "    xformedItems = dataMat.T * U[:,:4] * Sig4.I  #create transformed items\n",
    "    for j in range(n):\n",
    "        userRating = dataMat[user,j]\n",
    "        if userRating == 0 or j==item: continue\n",
    "        similarity = simMeas(xformedItems[item,:].T,\\\n",
    "                             xformedItems[j,:].T)\n",
    "        print('the %d and %d similarity is: %f' % (item, j, similarity))\n",
    "        simTotal += similarity\n",
    "        ratSimTotal += similarity * userRating\n",
    "    if simTotal == 0: return 0\n",
    "    else: return ratSimTotal/simTotal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 0 and 3 similarity is: 0.490950\n",
      "the 0 and 5 similarity is: 0.484274\n",
      "the 0 and 10 similarity is: 0.512755\n",
      "the 1 and 3 similarity is: 0.491294\n",
      "the 1 and 5 similarity is: 0.481516\n",
      "the 1 and 10 similarity is: 0.509709\n",
      "the 2 and 3 similarity is: 0.491573\n",
      "the 2 and 5 similarity is: 0.482346\n",
      "the 2 and 10 similarity is: 0.510584\n",
      "the 4 and 3 similarity is: 0.450495\n",
      "the 4 and 5 similarity is: 0.506795\n",
      "the 4 and 10 similarity is: 0.512896\n",
      "the 6 and 3 similarity is: 0.743699\n",
      "the 6 and 5 similarity is: 0.468366\n",
      "the 6 and 10 similarity is: 0.439465\n",
      "the 7 and 3 similarity is: 0.482175\n",
      "the 7 and 5 similarity is: 0.494716\n",
      "the 7 and 10 similarity is: 0.524970\n",
      "the 8 and 3 similarity is: 0.491307\n",
      "the 8 and 5 similarity is: 0.491228\n",
      "the 8 and 10 similarity is: 0.520290\n",
      "the 9 and 3 similarity is: 0.522379\n",
      "the 9 and 5 similarity is: 0.496130\n",
      "the 9 and 10 similarity is: 0.493617\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(4, 3.3447149384692278), (7, 3.3294020724526971), (9, 3.3281008763900686)]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recommend(myMat, 1, estMethod=svdEst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 0 and 3 similarity is: 0.341942\n",
      "the 0 and 5 similarity is: 0.124132\n",
      "the 0 and 10 similarity is: 0.116698\n",
      "the 1 and 3 similarity is: 0.345560\n",
      "the 1 and 5 similarity is: 0.126456\n",
      "the 1 and 10 similarity is: 0.118892\n",
      "the 2 and 3 similarity is: 0.345149\n",
      "the 2 and 5 similarity is: 0.126190\n",
      "the 2 and 10 similarity is: 0.118640\n",
      "the 4 and 3 similarity is: 0.450126\n",
      "the 4 and 5 similarity is: 0.528504\n",
      "the 4 and 10 similarity is: 0.544647\n",
      "the 6 and 3 similarity is: 0.923822\n",
      "the 6 and 5 similarity is: 0.724840\n",
      "the 6 and 10 similarity is: 0.710896\n",
      "the 7 and 3 similarity is: 0.319482\n",
      "the 7 and 5 similarity is: 0.118324\n",
      "the 7 and 10 similarity is: 0.113370\n",
      "the 8 and 3 similarity is: 0.334910\n",
      "the 8 and 5 similarity is: 0.119673\n",
      "the 8 and 10 similarity is: 0.112497\n",
      "the 9 and 3 similarity is: 0.566918\n",
      "the 9 and 5 similarity is: 0.590049\n",
      "the 9 and 10 similarity is: 0.602380\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(4, 3.3469521867021728), (9, 3.3353796573274703), (6, 3.3071930278130361)]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recommend(myMat, 1, estMethod=svdEst, simMeas=pearsSim)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printMat(inMat, thresh=0.8):\n",
    "    for i in range(32):\n",
    "        for k in range(32):\n",
    "            if float(inMat[i,k]) > thresh:\n",
    "                print(1, end=''),\n",
    "            else: print(0, end=''),\n",
    "        print('') \n",
    "\n",
    "def imgCompress(numSV=3, thresh=0.8):\n",
    "    myl = []\n",
    "    for line in open('0_5.txt').readlines():\n",
    "        newRow = []\n",
    "        for i in range(32):\n",
    "            newRow.append(int(line[i]))\n",
    "        myl.append(newRow)\n",
    "    myMat = mat(myl)\n",
    "    print(\"****original matrix******\")\n",
    "    printMat(myMat, thresh)\n",
    "    U,Sigma,VT = la.svd(myMat)\n",
    "    SigRecon = mat(zeros((numSV, numSV)))\n",
    "    for k in range(numSV):#construct diagonal matrix from vector\n",
    "        SigRecon[k,k] = Sigma[k]\n",
    "    reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:]\n",
    "    print(\"****reconstructed matrix using %d singular values******\" % numSV)\n",
    "    printMat(reconMat, thresh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "****original matrix******\n",
      "00000000000000110000000000000000\n",
      "00000000000011111100000000000000\n",
      "00000000000111111110000000000000\n",
      "00000000001111111111000000000000\n",
      "00000000111111111111100000000000\n",
      "00000001111111111111110000000000\n",
      "00000000111111111111111000000000\n",
      "00000000111111100001111100000000\n",
      "00000001111111000001111100000000\n",
      "00000011111100000000111100000000\n",
      "00000011111100000000111110000000\n",
      "00000011111100000000011110000000\n",
      "00000011111100000000011110000000\n",
      "00000001111110000000001111000000\n",
      "00000011111110000000001111000000\n",
      "00000011111100000000001111000000\n",
      "00000001111100000000001111000000\n",
      "00000011111100000000001111000000\n",
      "00000001111100000000001111000000\n",
      "00000001111100000000011111000000\n",
      "00000000111110000000001111100000\n",
      "00000000111110000000001111100000\n",
      "00000000111110000000001111100000\n",
      "00000000111110000000011111000000\n",
      "00000000111110000000111111000000\n",
      "00000000111111000001111110000000\n",
      "00000000011111111111111110000000\n",
      "00000000001111111111111110000000\n",
      "00000000001111111111111110000000\n",
      "00000000000111111111111000000000\n",
      "00000000000011111111110000000000\n",
      "00000000000000111111000000000000\n",
      "****reconstructed matrix using 2 singular values******\n",
      "00000000000000000000000000000000\n",
      "00000000000000000000000000000000\n",
      "00000000000001111100000000000000\n",
      "00000000000011111111000000000000\n",
      "00000000000111111111100000000000\n",
      "00000000001111111111110000000000\n",
      "00000000001111111111110000000000\n",
      "00000000011110000000001000000000\n",
      "00000000111100000000001100000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001110000000\n",
      "00000000111100000000001100000000\n",
      "00000000001111111111111000000000\n",
      "00000000001111111111110000000000\n",
      "00000000001111111111110000000000\n",
      "00000000000011111111100000000000\n",
      "00000000000011111111000000000000\n",
      "00000000000000000000000000000000\n"
     ]
    }
   ],
   "source": [
    "imgCompress(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
